Logarithm is Big \(O\) Of Any Positive Power
Theorem
For any \(\epsilon > 0\), \(\ln(x) < x^\epsilon\) for sufficiently large \(x\), and hence \(\log(x) = O(x^\epsilon)\).
Proof
From L'Hopital's rule, we have
\[ \lim_{x \to \infty} \frac{\ln(x)}{x^\epsilon} = \lim_{x \to \infty} \frac{x^{-1}}{\epsilon x^{\epsilon - 1}} = \lim_{x \to \infty} \frac{1}{\epsilon x^\epsilon} = 0\]
because \(\epsilon > 0\).
As such, there exists an \(x_0\) such that
\[ x > x_0 \implies \frac{\ln(x)}{x^\epsilon} < 1 \implies \ln(x) < x^\epsilon.\]
Any logarithm differs from the natural logarithm by a constant, and hence the above proves \(\log(x) = O(x^\epsilon)\).